# !/usr/bin/env python
# -*- coding:utf-8 -*-
# @FileName : code.py
# @Time     : 2024/3/5 22:29
# @Author   : Robot-Zsj
"""
description:

方法一：优先队列实现的Dijkstra算法

思路：

正数权值的连通图中，求两点之间的最短路，很容易想到经典的[Dijkstra算法]。但是本题不仅仅是求出最短路，还要求出最短路径的数目。我们将在[Dijkstra算法]的基础上，进行一些变动，来求出最短路径的数目。

[Dijkstra算法]：https://oi-wiki.org/graph/shortest-path/#Dijkstra-%E7%AE%97%E6%B3%95


优先队列实现的[Dijkstra算法]：

- e是邻接表
- q是优先队列
- dis用来记录源到各个点当前最短路径的长度
- vis用来记录哪些点的最短路径已经被确定。
- ways，ways[v]就表示源到点i最短的路径数目，且最短路径长度为dis[v]。ways的更新时机与dis相同。在访问当前点v的各个相邻点v时
    - 如果从点u到点v路径，能刷新dis[v]，则更新dis[v]，并将ways[v]更新为ways[u]，表示有多少条源到点u的最短路径，就有多少条源到点v的最短路径
    - 如果从点u到点v路径，与dis[v]相等。那么ways[v]的值要加上ways[v]，表示点u到点v路径贡献了另一部分源到点v的最短路径。
    - 如果从点u到点v路径，大于dis[v]。那么无需操作dis[v]。
"""
from heapq import heappop, heappush
from math import inf
from typing import List


class Solution:
    def countPaths(self, n: int, roads: List[List[int]]) -> int:
        mod = 10 ** 9 + 7
        e = [[] for _ in range(n)]
        for x, y, t in roads:
            e[x].append([y, t])
            e[y].append([x, t])
        dis = [0] + [inf] * (n - 1)
        ways = [1] + [0] * (n - 1)

        q = [[0, 0]]
        while q:
            t, u = heappop(q)
            if t > dis[u]:
                continue
            for v, w in e[u]:
                if t + w < dis[v]:
                    dis[v] = t + w
                    ways[v] = ways[u]
                    heappush(q, [t + w, v])
                elif t + w == dis[v]:
                    ways[v] = (ways[u] + ways[v]) % mod
        return ways[-1]


n = 7
roads = [[0, 6, 7], [0, 1, 2], [1, 2, 3], [1, 3, 3], [6, 3, 3], [3, 5, 1], [6, 5, 1], [2, 5, 1], [0, 4, 5], [4, 6, 2]]

print(Solution().countPaths(n, roads))
